package com.basicalg.impls;

import com.basicalg.helper.AlgHelper;
// 希尔排序是 插入排序的升级版， 设置大小为h的跨度，其中h是一个 递增函数 C * h +1 , C为常数
public class ShellSort {

    public static void sort(Comparable[] arr) {
        int h = 1;
        int N = arr.length;
        while (h < N / 3) h = h *3 +1;
        while (h >=1) {
            for (int i =h; i < N; i++) {
                for(int j =i; j>=h && AlgHelper.less(arr[j], arr[j-h]); j=-h ) {
                    AlgHelper.swap(arr, j, j-h);
                }
            }
            h = h /3;
        }
    }
}
